{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## heapq - Implements min-heap sort algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#generate some random data\n",
    "\n",
    "import random\n",
    "\n",
    "data = random.sample(range(100), 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[69, 21, 6, 91, 51, 55, 23, 61, 13, 57]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Shamelessly copied from Google search result ;)\n",
    "\n",
    "import math\n",
    "from io import StringIO\n",
    "\n",
    "\n",
    "def show_tree(tree, total_width=36, fill=' '):\n",
    "    \"\"\"Pretty-print a tree.\"\"\"\n",
    "    output = StringIO()\n",
    "    last_row = -1\n",
    "    for i, n in enumerate(tree):\n",
    "        if i:\n",
    "            row = int(math.floor(math.log(i + 1, 2)))\n",
    "        else:\n",
    "            row = 0\n",
    "        if row != last_row:\n",
    "            output.write('\\n')\n",
    "        columns = 2 ** row\n",
    "        col_width = int(math.floor(total_width / columns))\n",
    "        output.write(str(n).center(col_width, fill))\n",
    "        last_row = row\n",
    "    print(output.getvalue())\n",
    "    print('-' * total_width)\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "                 69                 \n",
      "        21                6         \n",
      "    91       51       55       23   \n",
      " 61  13  57 \n",
      "------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "show_tree(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Some random data: [69, 21, 6, 91, 51, 55, 23, 61, 13, 57]\n",
      "\n",
      "add 69\n",
      "\n",
      "                 69                 \n",
      "------------------------------------\n",
      "\n",
      "add 21\n",
      "\n",
      "                 21                 \n",
      "        69        \n",
      "------------------------------------\n",
      "\n",
      "add  6\n",
      "\n",
      "                 6                  \n",
      "        69                21        \n",
      "------------------------------------\n",
      "\n",
      "add 91\n",
      "\n",
      "                 6                  \n",
      "        69                21        \n",
      "    91   \n",
      "------------------------------------\n",
      "\n",
      "add 51\n",
      "\n",
      "                 6                  \n",
      "        51                21        \n",
      "    91       69   \n",
      "------------------------------------\n",
      "\n",
      "add 55\n",
      "\n",
      "                 6                  \n",
      "        51                21        \n",
      "    91       69       55   \n",
      "------------------------------------\n",
      "\n",
      "add 23\n",
      "\n",
      "                 6                  \n",
      "        51                21        \n",
      "    91       69       55       23   \n",
      "------------------------------------\n",
      "\n",
      "add 61\n",
      "\n",
      "                 6                  \n",
      "        51                21        \n",
      "    61       69       55       23   \n",
      " 91 \n",
      "------------------------------------\n",
      "\n",
      "add 13\n",
      "\n",
      "                 6                  \n",
      "        13                21        \n",
      "    51       69       55       23   \n",
      " 91  61 \n",
      "------------------------------------\n",
      "\n",
      "add 57\n",
      "\n",
      "                 6                  \n",
      "        13                21        \n",
      "    51       57       55       23   \n",
      " 91  61  69 \n",
      "------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "#create heap\n",
    "'''using heappush() and heapify()'''\n",
    "\n",
    "import heapq\n",
    "\n",
    "print('Some random data:', data)\n",
    "print()\n",
    "\n",
    "heap = []\n",
    "for n in data:\n",
    "    print('add{:>3}'.format(n))\n",
    "    heapq.heappush(heap, n)\n",
    "    show_tree(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Saved Data: [69, 21, 6, 91, 51, 55, 23, 61, 13, 57]\n",
      "Heapified data:\n",
      "\n",
      "                 6                  \n",
      "        13                23        \n",
      "    21       51       55       69   \n",
      " 61  91  57 \n",
      "------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "#create heap using heapify if data is already saved \n",
    "\n",
    "print('Saved Data:', data)\n",
    "heapq.heapify(data)\n",
    "print('Heapified data:')\n",
    "show_tree(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element popped: 6\n",
      "\n",
      "                 13                 \n",
      "        21                23        \n",
      "    57       51       55       69   \n",
      " 61  91 \n",
      "------------------------------------\n",
      "\n",
      "Element popped: 13\n",
      "\n",
      "                 21                 \n",
      "        51                23        \n",
      "    57       91       55       69   \n",
      " 61 \n",
      "------------------------------------\n",
      "\n",
      "Element popped: 21\n",
      "\n",
      "                 23                 \n",
      "        51                55        \n",
      "    57       91       61       69   \n",
      "------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Accessing heap elements - use heappop()\n",
    "\n",
    "for i in range(3):\n",
    "    smallest_number = heapq.heappop(data)\n",
    "    print('Element popped:', smallest_number)\n",
    "    show_tree(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Replace 23 with 2\n",
      "\n",
      "                 2                  \n",
      "        51                55        \n",
      "    57       91       61       69   \n",
      "------------------------------------\n",
      "\n",
      "Replace 2 with 6\n",
      "\n",
      "                 6                  \n",
      "        51                55        \n",
      "    57       91       61       69   \n",
      "------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Replacing heap elements\n",
    "\n",
    "for i in [2, 6]:\n",
    "    repl = heapq.heapreplace(data, i)\n",
    "    print('Replace {} with {}'.format(repl, i))\n",
    "    show_tree(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6, 51, 55, 57, 91, 61, 69]\n",
      "[91, 69, 61]\n",
      "[6, 51, 55]\n"
     ]
    }
   ],
   "source": [
    "# Get min - max elements from heap\n",
    "\n",
    "print(data)\n",
    "print(heapq.nlargest(3, data))\n",
    "print(heapq.nsmallest(3, data))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0: [33, 58, 71, 88, 95]\n",
      "1: [10, 11, 17, 38, 91]\n",
      "2: [13, 18, 39, 61, 63]\n",
      "3: [20, 27, 31, 42, 45]\n",
      "Merged lists:\n",
      "10 11 13 17 18 20 27 31 33 38 39 42 45 58 61 63 71 88 91 95 \n"
     ]
    }
   ],
   "source": [
    "# Merge sorted sequences\n",
    "random.seed(2016)\n",
    "dat = []\n",
    "for i in range(4):\n",
    "    new_data = list(random.sample(range(1, 101), 5))\n",
    "    new_data.sort()\n",
    "    dat.append(new_data)\n",
    "    \n",
    "for i, d in enumerate(dat):\n",
    "    print('{}: {}'.format(i, d))\n",
    "    \n",
    "print('Merged lists:')\n",
    "for i in heapq.merge(*dat):\n",
    "    print(i, end=' ')\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
